package LC_plus;

public class LC706_排序 {
    //链表节点
    private class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //数组长度
    private final int N = 10000;
    private Node[] node;

    public LC706_排序() {
        node = new Node[N];
    }

    //哈希函数
    private int hash(int key) {
        return key % N;
    }

    public void put(int key, int value) {
        int hash = hash(key);
        if (node[hash] == null) {
            //先存虚拟头
            node[hash] = new Node(-1, -1);
            //再存实际头节点
            node[hash].next = new Node(key, value);
        } else {
            //从虚拟头开始遍历
            Node prev = node[hash];
            Node temp = prev;
            while (temp.next != null) {
                if (temp.next.key == key) {
                    //有键，更新值
                    temp.next.value = value;
                    //按value进行排序，归并排序
                    prev.next = sortList(prev.next);
                    return;
                }
                temp = temp.next;
            }
            //没有键，添加节点
            temp.next = new Node(key, value);
        }
    }

    public Node sortList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node slow = head;
        Node fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node tmp = slow.next;
        slow.next = null;
        Node left = sortList(head);
        Node right = sortList(tmp);
        Node pre = new Node(0, 0);
        Node res = pre;
        while (left != null && right != null) {
            //小于0，升序。大于等于0，降序
            if (left.value < right.value) {
                pre.next = left;
                left = left.next;
            } else {
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        pre.next = left != null ? left : right;
        return res.next;
    }

    public int get(int key) {
        int hash = hash(key);
        if (node[hash] != null) {
            Node cur = node[hash].next;
            while (cur != null) {
                if (cur.key == key) {
                    return cur.value;
                }
                cur = cur.next;
            }
        }
        return -1;
    }

    public void remove(int key) {
        int hash = hash(key);
        if (node[hash] != null) {
            Node prev = node[hash];
            while (prev.next != null) {
                //删除节点
                if (prev.next.key == key) {
                    Node delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                    return;
                }
                prev = prev.next;
            }
        }
    }
}
